package 面试题53_1_数字在排序数组中出现的次数.非递归实现;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 13:37 2021/2/6
 * @Description：
 */
public class Solution {

    public int search(int[] nums, int target) {
        int res = -1;

        if (nums.length == 0) {
            return res;
        }

        int leftIndex = binary_search_leftBound(nums, target);
        int rightIndex = binary_search_rightBound(nums, target);
        if (leftIndex != -1 && rightIndex != -1) {
            return rightIndex - leftIndex + 1;
        }

        return res;
    }

    // 二分查找指定值的左边界值索引
    private int binary_search_leftBound(int[] data, int target) {
        int resultIndex = -1;

        int lowIndex = 0;
        int highIndex = data.length - 1;

        while (lowIndex < highIndex) {
            int midIndex = (lowIndex + highIndex) / 2; //取偏左的值
            if (data[midIndex] >= target) {
                highIndex = midIndex;
            } else if (data[midIndex] < target) {
                lowIndex = midIndex + 1;
            }
        }
        if (data[lowIndex] == target) {
            resultIndex = lowIndex;
        }

        return resultIndex;
    }

    private int binary_search_rightBound(int[] data, int target) {
        int resultIndex = -1;

        int lowIndex = 0;
        int highIndex = data.length - 1;

        while (lowIndex < highIndex) {
            int midIndex = (lowIndex + highIndex + 1) / 2;// 取偏右的值

            if (data[midIndex] > target) {
                highIndex = midIndex - 1;
            } else if (data[midIndex] <= target) {
                lowIndex = midIndex;
            }
        }

        if (data[highIndex] == target) {
            resultIndex = highIndex;
        }
        return resultIndex;
    }
}
